package day_2022_4_to_7.nowcoder;

import java.util.ArrayList;
import java.util.Stack;

class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}

/**
 * 从尾到头打印链表
 *
 * @author haomin
 * @date 2022/04/09 17:11
 **/
public class PrintArray {
    // 方法一 栈
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        Stack<Integer> stack = new Stack<>();
        ListNode node = listNode;
        // 先入栈
        while (node != null) {
            stack.push(node.val);
            node = node.next;
        }

        // 然后出栈
        ArrayList<Integer> list = new ArrayList<>();
        while (!stack.isEmpty()) {
            list.add(stack.pop());
        }
        return list;
    }


    // 方法二 逆置数组
    public ArrayList<Integer> printListFromTailToHead2(ListNode listNode) {
        ArrayList<Integer> list = new ArrayList<>();
        // 顺序存储
        while (listNode != null) {
            list.add(listNode.val);
            listNode = listNode.next;
        }

        int l = 0;
        int r = list.size() - 1;
        // 逆置数组
        while (l < r) {
            Integer temp = list.get(l);
            list.set(l, list.get(r));
            list.set(r, temp);
            l++;
            r--;
        }
        return list;
    }

    // 方法三 递归
    public ArrayList<Integer> printListFromTailToHead3(ListNode listNode) {
        ArrayList<Integer> list = new ArrayList<>();
        printListFromTailToHeadHelper(listNode,list);
        return list;
    }

    private void printListFromTailToHeadHelper(ListNode listNode, ArrayList<Integer> list) {
        if(listNode == null){
            return;
        }
        printListFromTailToHeadHelper(listNode.next,list);
        list.add(listNode.val);
    }

    // 方法四 逆置链表（回文）
    public ArrayList<Integer> printListFromTailToHead4(ListNode listNode) {
        ListNode dummyHead = new ListNode(-1);
        while (listNode != null){
            ListNode node = new ListNode(listNode.val);
            node.next = dummyHead.next;
            dummyHead.next = node;
            listNode = listNode.next;
        }
        ArrayList<Integer> list = new ArrayList<>();
        ListNode newNode = dummyHead.next;
        while (newNode != null){
            list.add(newNode.val);
            newNode = newNode.next;
        }
        return list;
    }
}


